package recursion;

/**
 * Created by IntelliJ IDEA.
 * User: 杰哥
 * Date: 2020/4/1
 * Time: 21:55
 * 八皇后问题
 */
public class Queen8 {

    //定义一个max表示共有多少个皇后
    int max = 8;
    //定义数组array ，保存皇后放置的结果,比如 arr = {0, 4, 7, 5, 2, 6, 1, 3}
    /*表示第一个皇后摆放在第1行下标0的列的位置
        第二个皇后摆放在第2行下标为4的列的位置
        第三个皇后摆放在第2行下标为7的列的位置*/
    int[] array = new int[max];
    int count = 0;
    public static void main(String[] args) {
        Queen8 q8 = new Queen8();
        q8.check(0);
        System.out.printf("共有%d种解法", q8.count);
    }

    //编写一个方法，放置皇后
    private  void check(int n) {
        if(n == max) { //当n=0时，说明已经放好了0至7共8个
            print();   //输出无冲突的摆放
            count++;   //统计解法次数
            return;
        }
        for(int i = 0; i < max; i++) { //从下标0的列开始摆放，直到下标为7的列
            /**
             * 比如先放第一列，同过 judge 方法判断是否冲突，冲突就不进if
             * 则摆放下列表(第二列)，再判断是否冲突，如果不冲突则 调用 check(n+1) 开始摆放下一个
             *
             * 如果在摆放第下标n行的皇后(就是摆放第n+1个皇后)时，
             * for循环完毕都没有进判断，说明在这一行无论放哪一列都不行，
             * 则会会到放第下标 n-1 行的皇后(就是摆放第n个皇后)时，然后进行循环，也就是
             * 不放原来所有在的列，往后面的列继续判断，如果不行则回到
             * 放 n -2 行的皇后时，再进行同样的操作。
             */
            array[n] = i;
            if(judge(n)){
                check(n + 1);
            }
        }
    }

    //查看当放置第n个皇后，就去检测该皇后是否和前面已经摆放的冲突
    private boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            /**
             * 说明:
             * 1. array[n] == array[i]，判断两个皇后所在列的下标是否相等，相等则在同一列
             * 2. Math.abs(n-i) == Math.abs(array[n]-array[i])
             *    判断是否在同一斜线上，两个皇后同一斜线上，则两个皇后行下标差等于列下标差
             */
            if(array[n] == array[i] || Math.abs(n-i) == Math.abs(array[n]-array[i]))  {
                return false;
            }
        }
        return true;
    }

    public  void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

}
